1. Field of the Invention
This invention relates generally to the field of communications. In particular, the invention relates to digital communication systems capable of encoding digital communication signals.
2. Related Art
The utilization of digital communication systems is growing at a rapid pace in today's society. Specifically, digital communication systems are becoming more common because they typically provide a higher level of performance than analog communication systems. Common examples of digital communication systems include digital radios, digital cellular telephones (utilizing frequency division multiple access “FDMA,” time division multiple access “TDMA,” code division multiple access “CDMA,” global system for mobile communications “GSM,” etc.), digital modems (utilizing such modulation schemes such as V.34, V.90, V.92, xDSL, etc.), satellite communications, and digital reproduction systems (i.e., compact disk “CD,” digital video disks “DVD,” digital audio tape “DAT,” digital video “DV,” MPEG, MP3, digital television “DTV,” high-definition television “HDTV,” etc.).
Digital communication systems generally provide a higher level of performance because they utilize digital modulation (such as amplitude phase keying “APK,” phase shift keying “PSK,” frequency shift keying “FSK,” pulse coded modulation “PCM,” pulse amplitude modulation “PAM,” quadrature amplitude modulation “QAM,” or a similar modulation scheme). Further, error detection and correction techniques allow for increased quality transmission of information data in a transmitting environment such as a communication channel. Typically, these digital communication systems utilize digital encoding schemes that reduce the effects of noise. These encoding schemes may include dependency among a large number of the transmitted digital symbols, thus enabling the receiver to make a more accurate detection of the received symbols. This is generally known as “error control coding” or utilizing “error correction code techniques.”
FIG. 1 shows an example implementation of a known digital communication system 100. In FIG. 1, communication occurs via the transmission of data information 102 from a transmitter 104 to a receiver 106, over a channel 108. The transmission is generally a random experiment because the transmitter 104 typically transmits one of a number of possible messages that depend on the data information 102 (that is not known ahead of time). The receiver 106 has no knowledge of which message is transmitted by the transmitter 104, however, the transmitted message is chosen from a set of messages that are known to both the transmitter 104 and the receiver 106. The transmitted message depends in part on the modulator 110 and may be an information data signal that is modulated by a carrier wave signal. The carrier wave signal is determined by the modulation scheme utilized by the modulator 110 such as, for example, APK, PSK, FSK, PCM, PAM, QAM or other similar schemes. Additionally, the transmitted message is received by a demodulator and detector 112 at the receiver 106. The demodulator and detector 112 demodulates the received signal utilizing a demodulation scheme that corresponds to the modulation scheme of the modulator 110. After demodulation, the demodulator and detector 112 detects the received information data signal.
Error control coding is utilized to reduce the effects of errors in the data transmission and reception because the data information transmitted to the receiver 106 should be received ideally at the receiver without any errors. However, if errors exist in the data transmission, error control coding helps detect and/or remove the errors at the receiver. The error control coding may include, as an example, block coding, concatenated coding, waveform coding, turbo coding and convolution coding, all of which are well known in the art. As a result, FIG. 1 shows that transmitter 104 may include an encoder 114 and that the receiver 106 may include a decoder 116.
Besides improved resistance to channel noise, digital communication systems also include the advantages of improved resistance to interference, increased capacity, and improved security of communication through the utilization of encryption. Digital communication techniques generally optimize the data throughput of a digital communication system that has a limited signal-to-noise ratio (“SNR” or “S/N”). Encoding techniques further allow the digital communication system to make tradeoffs between smaller SNRs or higher data rates that may be utilized with a same bit-error rate (“BER”).
In general, a convolutional encoder maps a signal composed of a k-bit sequence of input data bits (“k”) to a unique n-bit sequence of data bits (“n”) based on a convolution of the input sequence, k, with itself or with another signal. The amount of redundancy introduced by the encoding of the data is measured by the ratio “n/k.” The reciprocal of this ratio, k/n, is known as the “code rate.” The convolutional encoder generates a convolutional code by passing k through a linear finite-state shift register. In general, the shift register consists of K (k-bit) stages and n linear algebraic function generators. Typically, K is known as the “constraint length” and it represents the number of k-tuple stages in the shift register. The constraint length represents the number of k-bit shifts over which a single information bit may influence the encoder output. However, if the encoder includes “M” memory units (not shown) the “constraint length” is typically defined as M+1 instead of K. FIG. 2 shows an example of a typical convolutional encoder 200 with constraint length K and rate k/n.
In FIG. 2, a kK-stage shift register 202 is shown in signal communication with n modulo-2 adders 204, 206 and 208. The kK-stage shift register is a linear finite-state shift register with kK bit locations (several of which are labeled 210, 212, 214 and 216 ). At each unit of time, k bits 218 are shifted into the first k stages 210, 212 and 214 of the register 202; all the bits in the register 202 are shifted k stages to the right, and the outputs 220, 222 and 224 of the n adders 204, 206 and 208 are sequentially sampled, by a sampler 226, to yield the binary code symbols or code bits 228. These code symbols 228 are then utilized by the modulator (not shown) to specify the waveforms to be transmitted over the channel (not shown). Since there are n code bits for each input group of k message bits, the code rate is k/n message bit per code bit, where k<n. FIG. 3 shows another example of a convolution-type encoder 300.
In FIG. 3, the example encoder 300 includes three memory units M1 302, M2 304 and M3 306 and two adders 308 and 310. As an example, if the encoder 300 utilizes four functions “A,”“B,”“C” and “D,” the input 312 to the encoder 300 may be defined as “U” and the state of the encoder 300 may be defined as “S.” As a result, it is appreciated by those skilled in the art that the next state of the encoder 300 would be equal to A(S) plus B(U) and the output 314 of the encoder 300 would be equal to C(S) plus D(U). As such, encoder 300 may utilize any code represented by a trellis diagram.
The decoder 116, FIG. 1, decodes the demodulated and detected signal 118 output by the demodulator and detector 112. The demodulated and detected signal 118 is a received version of the n-bit sequence of data bits 120 produced by the encoder 114. It is appreciated by those skilled in the art, that for rate k/n codes, which are typically represented by a trellis diagram, the decoder 116 may utilize a Maximum Likelihood Sequence Estimator (such as the well known “Viterbi” algorithm) or a Maximum “A Posteriori” decoder (such as the “BCJR” algorithm described in “Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate,” by L. R. Bahl, J. Cocke, F. Jelinek and J. Raviv, pages 84-287, IEEE Transactions on Information Theory, published March of 1974, which herein incorporated by reference).
However, both of these decoding schemes are based on the unique trellis structure of the code. This unique trellis structure requires that the encoder 114 and decoder 116 utilize specialize hardware, that is configured for a specific code, to encode and decode the signal. Unfortunately, this results in lack of flexibility because the encoder 114 and decoder 116 must be designed and custom fabricated for a specific code.
Therefore there is a need for a multi-rate encoding and decoding system that allows the flexibility to utilize multiple types of convolution codes with the same hardware to balance the payload capacity of the system versus the operating SNR.
Past attempts to solve this problem have included utilizing punctured codes where single bits are deleted at intervals in a low-rate convolutional code. In this approach, a puncturing coder suppresses the bits for which the puncturing algorithm contains a “0” and transmits the bits for which the algorithm contains a “1.” Generally, punctured codes may be decoded in the same manner as the originally non-punctured code, however, in most situations there is a non-punctured code at the same rate that gives better performance, especially when trellis coded modulation (“TCM”) is utilized. Therefore, there is also a need for a multi-rate encoding and decoding system that is capable of utilizing multiple convolution codes with the same hardware and is of low complexity.